package algorithm.sort.child;

import algorithm.sort.basic.Sort;

/**
 * 项目名称: god
 * 包 名 称: algorithm.sort.child
 * 类 名 称: QuickSort
 * 类 描 述: TODO
 * 创建时间: 2020/6/25 6:13 下午
 * 创 建 人: Justice
 * 快速排序
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    // 对 [begin, end) 范围的元素进行快速排序
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        // 确定轴点位置 O(n)
        int middle = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, middle);
        sort(middle + 1, end);
    }

    // 构造出 [begin, end) 范围的轴点元素
    private int pivotIndex(int begin, int end) {
        // 随机选择轴点元素
        swap(begin, begin + (int) (Math.random() * (end - begin)));
        // 备份begin位置的元素
        T pivot = array[begin];
        end--;
        while (begin < end) {
            // 从右往左扫描
            while (begin < end) {
                // 右边元素 > 轴点元素
                if (cmp(pivot, array[end]) < 0) {
                    end--;
                } else {
                    // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                }
            }
            // 从左往右扫描
            while (begin < end) {
                // 左边元素 < 轴点元素
                if (cmp(pivot, array[begin]) > 0) {
                    begin++;
                } else {
                    // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        // 将轴点元素放入最终的位置
        array[begin] = pivot;
        // begin == end
        return begin;
    }
}
